package com.lwx.chapter3;

/**
 * 归并排序
 * 先划分为两个有序的数组，然后将这两部分有序的数组合并
 * nlogn 每次排序的时间复杂度O(n) 划分的层级为 logn层
 * 需要辅助空间
 */
public class mergeSort {
    public void mergeSort(int arr[], int n) {
        mergeSort(arr,0,n-1);
    }

    /**
     * 对 arr[l,...,r]的范围进行排序（前闭后闭）
     *
     * @param arr
     * @param l
     * @param r
     */
    public void mergeSort(int arr[], int l, int r) {
        if (l >= r) {
            return;
        }
        //当l和r是很大的int时,会发生溢出风险
        int mid = (l + r) / 2;
        mergeSort(arr,l,mid);
        mergeSort(arr,mid+1,r);
        merge(arr,l,mid,r);
    }

    /**
     * @param arr
     * @param left
     * @param mid   左边数组的最后一个元素
     * @param right
     */
    public void merge(int[] arr, int left, int mid, int right) {
        int[] aux = new int[right-left+1];
        int i = left;
        int j = mid + 1;
        for (int k = left; k <=right ; k++) {
            aux[k - left] = arr[k];
        }

        for (int k = left; k < right; k++) {
            if(i > mid){
                arr[k] = aux[j-left];
                j ++;
            }else if(j > right){
                arr[k]  = aux[i-left];
                i++;
            }
            if(aux[i-left] < aux[j-left]){
                arr[k] = aux[i-left];
                i++;
            }else {
                arr[k] = aux[j-left];
                j++;
            }
        }
        //临时数组的索引，指向下一个要放的元素的位置
//        int k = left;
//        while (i <= mid && j <= right) {
//            if (arr[i] <= arr[j]) {
//                aux[i-left] = arr[i];
//                i++;
//                k++;
//            } else {
//                aux[j-left] = arr[j];
//                j++;
//                k++;
//            }
//        }
//        int iIndex = i;
//        int jIndex = j;
//        while (i > mid) {
//            if (jIndex <= right) {
//                aux[k-left] = arr[jIndex++];
//                k++;
//            }
//        }
//        while (j > right) {
//            if (iIndex <= mid) {
//                aux[k-left] = arr[iIndex++];
//                k++;
//            }
//        }
//        int pIndex = left;
//        int kIndex = 0;
//        while (pIndex <= right) {
//            arr[pIndex++] = aux[kIndex++];
//        }

    }
}
